package com.arron.algorithm.leetcodetop100.数组.矩阵;

public class 搜索二维矩阵II {



    /**
     *   先将矩阵逆时针旋转45度，
     *   观察矩阵，其实就是一个二叉搜索树，每个节点的左节点比根节点小，右节点比根节点大 ，利用这个性质，从矩阵右上角开始遍历
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix_plus(int[][] matrix, int target) {

        int i = 0;
        int j = matrix[0].length-1;


        while (i<matrix.length && j>=0){

            if (matrix[i][j] <target){
                i++;
            }
            if (i == matrix.length){
                break;
            }
            if (matrix[i][j] > target){
                j--;
            }
            if (j <0){
                break;
            }
            if (matrix[i][j] == target){
                return true;
            }
        }

        return false;
    }




    /**
     *  使用二分查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix02(int[][] matrix, int target) {

        int rowIndex = 0;
        int colIndex = 0;

        while (rowIndex<matrix[0].length && colIndex < matrix.length){
            if (colSearch(colIndex,matrix,target)){
                return true;
            }
            if (rowSearch(rowIndex,matrix,target)){
                return true;
            }
            colIndex++;
            rowIndex++;
        }
        return false;
    }

    // 列查找
    public boolean colSearch(int col,int[][] matrix,int target){

        int left = col;
        int right = matrix.length-1;
        while (left<= right){
            int mid = left+(right-left)/2;

            if (matrix[mid][col] == target){
                return true;
            }else if (matrix[mid][col] <target){
                left = mid +1;
            }else {
                right = mid -1;
            }
        }

        return false;
    }

    // 列查找
    public boolean rowSearch(int row,int[][] matrix,int target){

        int left = row;
        int right = matrix[0].length-1;
        while (left<= right){
            int mid = left+(right-left)/2;

            if (matrix[row][mid] == target){
                return true;
            }else if (matrix[row][mid] <target){
                left = mid +1;
            }else {
                right = mid -1;
            }
        }

        return false;
    }

}
